package com.hyb.algorithm.data.struct.dp;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: huyanbing
 * @Date: 2021/8/12 5:59 下午
 */
public class OpenLock2 {

    public static void main(String[] args) {

        String[] deadends = new String[]{"0201", "0101", "0102", "1212", "2002"};
        String target = "0202";

        OpenLock2 openLock = new OpenLock2();
        System.out.println(openLock.openLock(deadends, target));
    }

    /**
     * 双向 BSF
     *
     * @param deadends
     * @param target
     * @return
     */
    int openLock(String[] deadends, String target) {
        Set<String> deads = new HashSet<>();
        for (String s : deadends) deads.add(s);
        // ⽤集合不⽤队列，可以快速判断元素是否存在
        Set<String> q1 = new HashSet<>();
        Set<String> q2 = new HashSet<>();
        Set<String> visited = new HashSet<>();
        int step = 0;
        q1.add("0000");
        q2.add(target);
        while (!q1.isEmpty() && !q2.isEmpty()) {
        // 哈希集合在遍历的过程中不能修改，⽤ temp 存储扩散结果
            Set<String> temp = new HashSet<>();
            /* 将 q1 中的所有节点向周围扩散 */
            for (String cur : q1) {
                /* 判断是否到达终点 */
                if (deads.contains(cur)) {
                    continue;
                }
                if (q2.contains(cur)) {
                    return step;
                }
                visited.add(cur);
                /* 将⼀个节点的未遍历相邻节点加⼊集合 */
                for (int j = 0; j < 4; j++) {
                    String up = plusOne(cur, j);
                    if (!visited.contains(up))
                        temp.add(up);
                    String down = minusOne(cur, j);
                    if (!visited.contains(down))
                        temp.add(down);
                }
            }
            /* 在这⾥增加步数 */
            step++;
            // temp 相当于 q1
            // 这⾥交换 q1 q2，下⼀轮 while 就是扩散 q2
            q1 = q2;
            q2 = temp;
        }
        return -1;
    }


    /**
     * 将 s[j] 向上拨动一次
     *
     * @param s
     * @param i
     * @return
     */
    public String plusOne(String s, int i) {

        char[] ch = s.toCharArray();

        if (ch[i] == '9') {
            ch[i] = '0';
        } else {
            ch[i] += 1;
        }

        return new String(ch);
    }


    /**
     * 将 s[i] 向下拨动一次
     *
     * @param s
     * @param i
     * @return
     */
    public String minusOne(String s, int i) {
        char[] ch = s.toCharArray();

        if (ch[i] == '0') {
            ch[i] = '9';
        } else {
            ch[i] -= 1;
        }

        return new String(ch);
    }

}
